/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//  ListNode * tmp = head->next;
//  head->next = nullptr;
//  tmp->next = head;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 双指针法
class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        ListNode *pre = nullptr;
        ListNode *cur = head;
        while (cur != nullptr)
        {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

// 递归法
ListNode *reverse(ListNode *pre, ListNode *cur)
{
    if (cur == nullptr)
        return pre;
    ListNode *tmp = cur->next;
    cur->next = pre;
    return reverse(cur, tmp);
}

class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        return reverse(nullptr, head);
    }
};